package leetcode;

import java.util.ArrayList;
import java.util.List;

public class LeetCodeMain97 {
    public boolean isPowerOfTwo(int n) {
        if (n<0){
            return false;
        }
        int count=0;
        while (n!=0){
            count++;
            n=n&(n-1);
        }
        return count==1;
    }
    public boolean canWinNim(int n) {
        if (n<=3){
            return true;
        }
        return n/4==0?false:true;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node=root;
        while (true){
            if (node.val>p.val&&node.val>q.val){
                node=node.left;
            }else if (node.val<p.val&&node.val<q.val){
                node=node.right;
            }else {
                break;
            }
        }
        return node;
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }
        int x=matrix.length-1;
        int y=matrix[0].length-1;
        int i=0;
        int j=0;
        List<Integer> list=new ArrayList<>();
        while (i<=x&&j<=y){
            for (int k = j; k <= y; k++) {
                list.add(matrix[i][k]);
            }
            i++;
            if (i>x){
                break;
            }
            for (int k = i; k <= x; k++) {
                list.add(matrix[k][y]);
            }
            y--;
            if (j>y){
                break;
            }
            for (int k = y; k >= j; k--) {
                list.add(matrix[x][k]);
            }
            x--;
            if (i>x){
                break;
            }
            for (int k = x; k >= i; k--) {
                list.add(matrix[k][j]);
            }
            j++;
        }
        return list;
    }
    public String multiply(String num1, String num2) {
        if ("0".equals(num1)||"0".equals(num2)){
            return "0";
        }
        String str="0";
        for (int i = num2.length()-1; i >= 0; i--) {
            char ch=num2.charAt(i);
            int sum=0;
            StringBuffer buffer=new StringBuffer();
            for (int j = num2.length()-1; j >i; j--) {
                buffer.append(0);
            }
            int num=ch-'0';
            for (int j = num1.length()-1; j >= 0; j--) {
                char ch2=num1.charAt(j);
                int num3=ch2-'0';
                sum=sum+num3*num;
                buffer.append(sum%10);
                sum=sum/10;
            }
            if (sum!=0){
                buffer.append(sum%10);
            }
            buffer.reverse();
            str=getSum(str,buffer.toString());
        }
        return str;
    }

    public String getSum(String num1,String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }
    public ListNode rotateRight1(ListNode head, int k) {
        int count=0;
        ListNode node=head;
        while (node!=null){
            count++;
            node=node.next;
        }
        if (count==0){
            return head;
        }
        k=k%count;
        ListNode[] arr=new ListNode[count];
        for (int i = 0; i < count; i++) {
            arr[i]=head;
            head=head.next;
        }
        for (int i = 1; i <= k; i++) {
            ListNode node1=arr[count-1];
            for (int j = count-1; j >0 ; j--) {
                arr[j]=arr[j-1];
            }
            arr[0]=node1;
        }
        ListNode listNode=new ListNode(-1);
        ListNode listNode1=listNode;
        for (ListNode n1:arr) {
            listNode1.next=n1;
            listNode1=n1;
        }
        listNode1.next=null;
        return listNode.next;
    }
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int count=1;
        ListNode node=head;
        while (node.next!=null){
            count++;
            node=node.next;
        }
        if (count==0){
            return head;
        }
        k=k%count;
        if (k==0){
            return head;
        }
        node.next=head;
        for (int i = 0; i < count-k; i++) {
            node=node.next;
        }
        ListNode node1=node.next;
        node.next=null;
        return node1;
    }
    List<Integer> list=new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return list.get(k-1);
    }
    public void inOrder(TreeNode root,int k){
        if (root==null||k==list.size()){
            return;
        }
        inOrder(root.left,k);
        list.add(root.val);
        inOrder(root.right,k);
    }
}
